APPLESOFT ACADEMY
By Chris Birch
Copyright (c) 1991 Apple Users' Group, Sydney
Republished from Applecations, a publication of the Apple Users' Group, Sydney, Australia.
THIS MONTH'S LECTURE: Random Numbers
The second in a series exploring Applesoft - the native programming language of the Apple II family of computers. If you own or use an Apple II or compatible computer (including the Apple III or Mac LC with emulation or Laser, Redstone, etc.) then read on.
The minimum hardware requirements are a 40 column original, compatible or emulated Apple II family computer with 48K of RAM and a colour screen (television or monitor), DOS 3.3 and Applesoft.
An intermediate knowledge of Applesoft is all that is required. You should be able to type in, edit, LIST, RUN and SAVE an Applesoft program. Ideally, you want to graduate from your "Applesoft Tutorial" or "Touch of" manual and what better place to do this than from the Applesoft Academy!
Last time we concluded with a fun program that plotted random points on the high res screen to create a snow storm effect. The listing was as follows:
The program utilises the built in random number generator (RND) of Applesoft. The random number will always be less than one and greater than or equal to zero. This is why the random number is multiplied by the maximum value of the horizontal or vertical range. If the random number is always "a part of one" then we convert it into a part of 279 or a part of 159. The following algebraic expression illustrates this concept:
FIG1:
X RND(2)
------ = -----
279 1
The number is then converted from a fractional or REAL number into a whole or INTEGER number with the INT function. The INT function simply discards the fractional part without bothering to "round up" to the next larger integer for fractions greater than or equal to 0.5 and "round down" for fractions less than 0.5 as is the usual convention. Adding 0.5 is a useful programming trick that forces this rounding. If we did not add 0.5 then we would never obtain an X value of 279 or a Y value of 159.
The value in the RND parenthesis is important in dictating how the RND command will behave. Our options are simple. The number is either zero, any positive number or any negative number.
RND(0)
------
A value of zero as the "argument" for the RND function will cause the number returned from the previous RND to be repeated. To see this we'll run example 8:
EX8:
10 FOR I = 1 TO 22
20 X = RND(1)
30 Y = RND(0)
40 PRINT "X="; X, "Y="; Y
50 NEXT
Not an especially exciting example however it does illustrate the behaviour of the RND(0) command.
Despite its apparent simplicity the program will not necessarily display 22 lines of information. If a number is very small then the one line of output will become two because Applesoft will display X and Y in scientific notation. You might have to run the program many times to see this happen. You should allow for this possibility in any of your programs.
RND(positive)
-------------
A positive RND argument will cause a different random number to be returned each time the RND function is executed. That is the basis upon which Example 7 is built. It does not matter if the positive argument is the same each time.
RND(negative)
-------------
When you use a negative RND argument then a random number will be returned as normal but it will be the same random number each time you use the same argument. Example 9 illustrates this and once again the value of X should always be the same as the Y value:
EX9:
10 FOR I = 1 TO 22
20 S = RND(1)
30 X = RND( -S)
40 Y = RND( -S)
50 PRINT "X="; X, "Y="; Y
60 NEXT
Another important feature to note is that the random number that is returned by the RND(-ve) command is just one of a predetermined sequence of random numbers - just like a
printed table of random numbers. To get the next random number in the sequence you simply invoke the RND function again with a positive argument. To obtain the second and subsequent random numbers in the sequence you continue to use a positive argument.
EX10:
10 FOR J = 1 TO 2
20 S = RND(-1)
30 FOR I = 1 TO 11
40 X = RND(2)
50 PRINT "X=";X
60 NEXT
70 NEXT
Example 10 has two loops. The outside FOR loop causes lines 20 through to 60 to be executed twice. The variable J will have a value of 1 the first time through the loop and a value of 2 the second time through the loop. Note that J is not actually used anywhere else in this program. Its use, in this example, is restricted merely in causing the FOR loop to tick over.
Within this loop the other loop prints the first 11 random numbers for the "-1" series of random numbers. This means that the same 11 random numbers should appear twice. Furthermore, the same numbers will be returned if you run the program tomorrow, the day after or next year. They are:
(Advanced: All the examples are tested on a range of Apple II family computers. If your computer should give output different to this example or any other example then please contact the author)
Ordered random numbers
---------------------
Applesoft was designed to run on systems with as little as 16K of memory. Intuitively (i.e. on the basis of a very good hunch based upon experience) we could suspect that all the numbers in the many possible sequences of random numbers are not stored in the computer. They are calculated according to
a mathematical formula. These austere beginnings are the reason why Example 10 is infinitely reproducible.
This author believed that the ordered sequence of random numbers was also a repeating sequence. This would mean that the numbers in Figure 2 occur again if the upper limit of 11 in Example 10 is extended. The question is how many numbers occur before they repeat. Empirical (i.e. show by way of experiment) evidence showed that the limit is above 60 million. This indeed suggests each number is unique.
Patient readers may wish to run Example 11 and wait for the program to terminate. The program will achieve around 198,000 iterations (i.e. times through the program loop at lines 30 and 40) per hour on a standard Apple II+.
EX11:
10 X = RND(-1)
20 PRINT "THE FIRST ONE IS "; X
30 Z = RND(2)
40 IF Z <> X THEN Y = Y + 1: PRINT Y: GOTO 30
50 PRINT "THERE ARE "; Y; " NUMBERS IN THE" : PRINT "SEQUENCE"
Poor Distribution
-----------------
Lets look again at our snow storm program. Now would be a good time to run Example 7 again. Look carefully this time and you will notice that the screen is never actually filled with snow. It seems to stabilise after a while. In fact, as with Example 10, the same pattern of snow and dark patches will occur each time you run the program.
A fundamental flaw in Applesoft's random number generator is now readily apparent. The formula hidden away in the Applesoft Firmware is capable of generating many millions of unique numbers but this feature alone is not the only precondition for a random number generator to be truly random.
To fully explain this flaw a parallel will be drawn with results of a school exam. Assume a class has sat an exam where the possible marks range from 0 to 100. For whatever reason, the examiner decides to group certain ranges of marks together. A score of 85 or over will be deemed a "high distinction", 75 - 84 a "distinction", 65 - 74 a "credit", 50 - 64 a "pass" and 0 to 49 a "fail".
Example 7 also grouped the exam results or random numbers together. With a little mathematical trickery, instead of there being 5 ranges of exam marks there were 280 ranges for X and 160 ranges for Y. If the random number generator returned a value of 0.535536507 in line 30 of Example 7 then this would result in an X value of 149. Yet values of 0.535842293 or 0.532258065 will also yield 149. Millions of values for the result of the RND function could yield the same X coordinate (or Y coordinate).
Now suppose that whenever a certain student's paper is marked, the next student's paper is always slightly less
than the previous student's paper. This happens in every exam. If the two students were in adjacent seats then the teacher could suspect the second student copies off the first student or in other words, there is a flaw in the procedure warranting further investigation.
Similarly, the presence of black holes in Example 7 means that when a certain value of X occurs the next random number (plotted as Y) will never occur for certain values of Y and we should also be suspicious. In other words, for a given value of the RND function, the next result of the RND function will never yield a value over certain, predictable ranges of numbers. This is hardly random, particularly when there are so many of these excluded ranges and many millions of values in each of these ranges.
(Advanced: You could try to experimentally determine how large a range of excluded succeeding values is by adjusting Example 7 to plot a smaller number of coordinates or ranges. You could also try equal X and Y ranges to assist in visualising any patterns.)
With the origins of Applesoft in mind, the random number generator does very well to achieve its "randomness". This month's lecture judged randomness on an intuitive or empirical level. There is no such thing as a mathematical formula or test that will conclusively determine that the random number generator is random.
(Advanced: The best treatment of randomness is in "Statistical Theory", Section 11.3, by Bernard W. Lindgren, Collier & Macmillan. This is a university text written with precision and clarity with emphasis on the exposition of proven statistical theorems presented in an historical order. Lindgren does put forward many tests that judge certain aspects of randomness. With a suitable choice of tests a scientist would still only be able to conclude intuitively that there is sufficient randomness).
What's Next?
------------
So far we have studied high resolution graphics and random numbers at the Applesoft Academy. You would agree that they are easy to implement yet extremely complex when it comes to understanding their finer points. Next time we will examine how to best combine Applesoft commands into a well structured, readable and maintainable program. The techniques we will use are those used by thousands of programmers world wide who "cut code" for a living. Everybodys' coding techniques for everybodys' programming language - Applesoft!
Permission is hereby granted for non-profit user groups to republish this content. PLEASE CREDIT THE AUTHOR AND THE SOURCE: Applecations, publication of the Apple Users' Group, Sydney, Australia